package com.wuyou.mid;

import cn.hutool.crypto.digest.HMac;
import cn.hutool.crypto.digest.HmacAlgorithm;

import java.io.IOException;
import java.security.InvalidKeyException;

/**
 * 1139. 最大的以 1 为边界的正方形
 */
public class Largest1BorderedSquare {

    public static void main(String[] args) throws IOException, InvalidKeyException {
//        int[][] grid = {{1, 1}, {1, 0}}; // 1
//        int[][] grid = {{1,1,1},{1,0,1},{1,1,1}};// 9
//        int[][] grid = {{0}};// 0
        int[][] grid = {{0, 0}, {0, 1}};// 1
//
//        System.out.println(sol_1(grid));

        System.out.println(System.currentTimeMillis());
    }


    public static int sol_1(int[][] grid) {
        int res = 0;

        int i = 0;
        while (i < grid.length) {
            // 查找第i行数据
            int j = i;
            int wL = j, wR = j, wLen = 0;
            while (j < grid[i].length) {
                int tempL = j, tempR = j, tempIndex = j;
                while (tempIndex < grid[i].length && grid[i][tempIndex] == 1) {
                    tempR = tempIndex;
                    tempIndex ++;
                    // 初始化返回结果为1
                    res = 1;
                }
                if (wLen < tempR - tempL) {
                    wL = tempL;
                    wR = tempR;
                    wLen = wR - wL;
                    j = wR;
                } else {
                    j++;
                }
            }
            // 查找第i列数据
            int k = i;
            int hL = k, hR = k, hLen = 0;
            while (k < grid.length) {
                int tempL = k, tempR = k, tempIndex = k;
                while (tempIndex < grid.length && grid[tempIndex][i] == 1) {
                    tempR = tempIndex;
                    tempIndex ++;
                    // 初始化返回结果为1
                    res = 1;
                }
                if (hLen < tempR - tempL) {
                    hL = tempL;
                    hR = tempR;
                    hLen = hR - hL;
                    k = hR;
                } else {
                    k++;
                }
            }
            int l = 0, r = 0, len = 0;
            if (hLen < wLen) {
                l = hL;
                r = hR;
                len = hLen;
            } else {
                l = wL;
                r = wR;
                len = wLen;
            }
            i = r + 1;
            int side = squareSide(grid, l, r);
            if (side != -1) {
                res = Math.max(res, side*side);
            }
        }
        return res;
    }

    public static int squareSide(int[][] grid, int l, int r) {
        int count = 0;
        int wSide = 0, hSide = 0;
        for (int i = l; i <= r; i++) {
            count ++;
            if (grid[r][i] == 0) {
                return i > l ? 1 : -1;
            }
            wSide = i;
        }
        for (int i = l; i <= r; i++) {
            count ++;
            if (grid[i][r] == 0) {
                return i > l ? 1 : -1;
            }
            hSide = i;
        }
        return count > 0 && wSide == hSide ? Math.min(wSide, hSide) + 1 : 0;
    }
}
